#!/usr/bin/env python3.3

from math import sqrt

def primeSieve(limit):
#  generates a list containing all primes from 2 to limit
  primes={0:False,1:False}
  for i in range(2,limit+1):
    primes[i]=True
  for i in range(len(primes)):
    if primes[i]:
      for j in range(i*2,limit+1,i):
        primes[j]=False
  return [k for k in primes.keys() if primes[k]]

def isPrime(n):
#  returnes True if n is a Prime
  if n<3:
    return n==2
  if n%2==0 or n%3==0:
    return False
  t=int(n**0.5)+1
  i=5
  while i<t:
    if n%i==0:
      return False
    i+=2
  return True

cfib={0:0,1:1}
def fib(k):
#  returns the k_th fibbonacci number
  if not k in cfib:
    cfib[k]=fib(k-2)+fib(k-1)
  return cfib[k]

def isPalindrome(n):
#  returns true if n is a palindrome
  s=str(n)
  return s==s[::-1]

def triangular(n):
#  returns the n_th triangular number
  return int((1+n)*n/2)

def square(n):
  return int(n*n)

def pentagonal(n):
  return int(n*(3*n-1)/2)

def hexagonal(n):
  return int(n*(2*n-1))

def heptagonal(n):
  return int(n*(5*n-3)/2)

def octagonal(n):
  return int(n*(3*n-2))

ccollatz={1:1}
def getCollatzLength(n):
#  returns the lenght of the colatz sequence for a givven number
  if n in ccollatz:
    return ccollatz[n]
  if n%2==0:
    ccollatz[n]=getCollatzLength(n//2)+1
  else:
    ccollatz[n]=getCollatzLength(n*3+1)+1
  return ccollatz[n]

cfak={0:1}
def fak(n):
#  returns the factorial of n
  if not n in cfak:
    cfak[n]=n*fak(n-1)
  return cfak[n]

cpropdivsum={1:0}
def getSumOfProperDivisors(n):
#  returnes the sum of all proper divisors of n
  if n in cpropdivsum:
    return cpropdivsum[n]
  cpropdivsum[n]=0
  r=int(sqrt(n))
  if r*r==n:
    cpropdivsum[n]=r+1
    r-=1
  else:
    cpropdivsum[n]=1
  if n%2!=0:
    x=3
    step=2
  else:
    x=2
    step=1
  for i in range(x,r+1,step):
    if n%i==0:
      cpropdivsum[n]+=i+n//i
  return cpropdivsum[n]

def isAbundantNumber(n):
  return getSumOfProperDivisors(n)>n

def isPerfectNumber(n):
  return getSumOfProperDivisors(n)==n

def isDeficientNumber(n):
  return getSumOfProperDivisors(n)<n

def isPandigital(n,start=1,stop=9):
  pd=[str(i) for i in range(start,stop+1)]
  l=[c for c in str(n)]
  l.sort()
  ll=len(l)
  if ll<1 or ll>(stop-start)+1:
    return False
  else:
    return l==pd[:ll]


if __name__=="__main__":
#  just for testing
#  runs only if euler.py is run directly
#  not if it is imported by any other *.py
  print("primeSieve(15): ",primeSieve(15))
  print("isPrime(997): ",isPrime(997))
  print("fib(10): ",fib(10))
  print("isPalindrome(8765678): ",isPalindrome(8765678))
  print("triangular(3): ",triangular(3))
  print("square(3): ",square(3))
  print("pentagonal(3): ",pentagonal(3))
  print("hexagonal(3): ",hexagonal(3))
  print("heptagonal(3): ",heptagonal(3))
  print("octagonal(3): ",octagonal(3))
  print("getCollatzLength(13): ",getCollatzLength(13))
  print("fak(10): ",fak(10))
  print("getSumOfProperDivisors(284): ",getSumOfProperDivisors(284))
  #missing isAbundant isPerfect and isDeficient number functions
  print("isPandigital(243658719): ",isPandigital(243568719))

